#include <vector>
using namespace std;
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n=s1.size(), m=s2.size();
        if (n==0) return s2==s3;
        if (m==0) return s1==s3;
        if (n+m!=s3.size()) return false;
        vector<vector<bool> > f(n+1, vector<bool>(m+1, false));
        f[0][0]=true;
        for (int i=1;i<=m;i++)
            f[0][i]=f[0][i-1] && (s2[i-1]==s3[i-1]);
        for (int i=1;i<=n;i++){
            f[i][0]=f[i-1][0] && (s1[i-1]==s3[i-1]);
            for (int j=1;j<=m;j++)
                f[i][j]=(f[i-1][j] && (s1[i-1]==s3[i+j-1])) || (f[i][j-1] && (s2[j-1]==s3[i+j-1]));
        }
        return f[n][m];
    }
};
